package leetcode_400;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 *@author 周杨
 *MinimumHeightTrees_310_ 给定一颗树 非二叉树 求该数所有节点  这些节点有个特点 以该节点为根 树的高度最大
 *describe:两种方法 1:任何树都只能有最多两个这种最高根节点 所以每次找叶子节点 用队列把边删掉 最后剩下两个节点或者一个节点为答案
 *			      2:递归 用dp数组保存已经求了的数的高度 把所有节点为根的高度求出来
 *2018年7月2日 下午2:55:55
 */
public class MinimumHeightTrees_310_ {

	public static void main(String[] args) {
		MinimumHeightTrees_310_ test=new MinimumHeightTrees_310_();
		List<Integer> res=test.findMinHeightTrees(6, new int[][] {{0, 3}, {1, 3}, {2, 3}
		, {4, 3}, {5, 4}});

	}
	/**
	 * describe:非递归方式 每次去掉叶子 并遍历这条唯一的边 去掉 直至剩下最后两个节点(或者1个) 
	 * 这种方法的核心思想是 任何树都只能有最多两个这种最高根节点 可惜的是 这种方法在最后一个用例中超时(其实还可以优化 思想不变 我没试过)
	 * 2018年7月2日 下午2:47:35
	 */
	public List<Integer> findMinHeightTrees(int n, int[][] edges) {
		List<Integer> res=new ArrayList<Integer>();
        List<List<Integer>> ed=new ArrayList<List<Integer>>();
        if(n==0)
        	return res;
        if(n==1){
            res.add(0);
            return res;
        }
        int count[]=new int[n];//用来记录度
        for(int i=0;i<edges.length;++i) {
        	count[edges[i][0]]++;
        	count[edges[i][1]]++;
        	List<Integer> list=new ArrayList<Integer>();
        	list.add(edges[i][0]);
        	list.add(edges[i][1]);
        	ed.add(list);//边补上
        }
        int mount=n;
        while(mount>2) {
        	Queue<Integer> queue=new LinkedList<Integer>();
        	for(int i=0;i<count.length;++i) {
        		if(count[i]==1) {//叶子
        			queue.add(i);
        		}
        	}
        	while(!queue.isEmpty()) {//删掉这些唯一边
    			int now=queue.poll();
    			for(int j=0;j<ed.size();++j) {
    				List<Integer> edge=ed.get(j);
    				if(edge.get(0)==now) {//找到这条唯一的边
    					count[edge.get(1)]--;
    					count[edge.get(0)]=-1;
    					mount--;
    					ed.remove(edge);
    					break;
    				}
    				if(edge.get(1)==now) {
    					count[edge.get(0)]--;
    					count[edge.get(1)]=-1;
    					mount--;
    					ed.remove(edge);
    					break;
    				}
    			}
    		}
        }
        for(int i=0;i<count.length;++i) {
        	if(count[i]!=-1)
        		res.add(i);
        }
        return res;
    }
	
	/**
	 * describe:上述方法的优化版
	 * 2018年7月2日 下午2:55:26
	 */
	public List<Integer> findMinHeightTrees1(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);
        List<Integer> leaves = new ArrayList<>();
        List<Set<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; ++i) adj.add(new HashSet<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        for (int i = 0; i < n; ++i) {
            if (adj.get(i).size() == 1) leaves.add(i);
        }
        while (n > 2) {
            n -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int i : leaves) {
                int t = adj.get(i).iterator().next();
                adj.get(t).remove(i);
                if (adj.get(t).size() == 1) newLeaves.add(t);
            }
            leaves = newLeaves;
        }
        return leaves;
    }
}
